#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
struct Node {
    int val;
    struct Node* next;
    struct Node* random;
};

typedef struct Node Node;

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
    {
        return NULL;
    }
    Node* pcur = head;
    Node* new = NULL;
    while (pcur)
    {
        new = (Node*)malloc(sizeof(Node));
        new->val = pcur->val;
        new->next = pcur->next;
        pcur->next = new;
        pcur = pcur->next->next;
    }
    pcur = head;
    while (pcur)
    {
        if (pcur->random != NULL)
        {
            pcur->next->random = pcur->random->next;
        }
        else
        {
            pcur->next->random = NULL;
        }
        pcur = pcur->next->next;
    }
    pcur = head;
    Node* pnext = pcur->next;
    Node* newlist = pnext;
    while (pnext->next)
    {
        pcur->next = pnext->next;
        pcur = pcur->next;
        pnext->next = pcur->next;
        pnext = pcur->next;
    }
    pcur->next = pnext->next;
    return newlist;
}